package my.jwds.p798;

import com.alibaba.fastjson.JSONObject;

import java.util.Arrays;

public class BestRotation {

    public static void main(String[] args) {

        BestRotation obj = new BestRotation();
        int [] nums = JSONObject.parseObject("[2,3,1,4,0]",int[].class);
        long start = System.currentTimeMillis();
        System.out.println(obj.bestRotation(nums));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    void add(int []c ,int l,int r){
        c[l] += 1;
        c[r+1] -=1;
    }
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] c = new int[n+1];
        for (int i = 0; i < n; i++) {
            int a = (i+1-n+n) % n, b = (i-nums[i]+n) % n;
            if (a <= b){
                add(c,a,b);
            }else{
                add(c,0,b);
                add(c,a,n-1);
            }
        }


        for (int i = 1; i < c.length; i++) {
            c[i] +=c[i-1];
        }

        int k = 0;
        for (int i = 1; i < c.length; i++) {
            if (c[k] < c[i]){
                k=i;
            }
        }
        return k;
    }


    static int N = 100010;
    static int[] c = new int[N];
    void add(int l, int r) {
        c[l] += 1; c[r + 1] -= 1;
    }
    public int bestRotation1(int[] nums) {
        Arrays.fill(c, 0);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int a = (i - (n - 1) + n) % n, b = (i - nums[i] + n) % n;
            if (a <= b) {
                add(a, b);
            } else {
                add(0, b);
                add(a, n - 1);
            }
        }
        for (int i = 1; i <= n; i++) c[i] += c[i - 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (c[i] > c[ans]) ans = i;
        }
        return ans;
    }



}